/* recursive sort */
/* input int num = number of elements */
/* input int* arr_ptr = array of elements for sorting */
/* output int error = error check code */

#include <stdio.h>
#include <stdlib.h>

int recursive_sort(int* buff, int num, int* arr_ptr) {
  int* front_ptr;
  int* half_ptr;
  int i, j=0, k=0, n=0;

  if( num==1 )
    buff[0] = arr_ptr[0];
  else if( num==2 ) {
    if( arr_ptr[0]<arr_ptr[1] ) {
      buff[0] = arr_ptr[0];
      buff[1] = arr_ptr[1];
    } else {
      buff[0] = arr_ptr[1];
      buff[1] = arr_ptr[0];
    }
  } else { // num >= 3
    n = num/2;
    front_ptr = calloc(n, sizeof(int));
    half_ptr = calloc((num-n), sizeof(int));

    recursive_sort(front_ptr, n, arr_ptr);
    recursive_sort(half_ptr, (num-n), (arr_ptr+n));

    // sort between two sorted array
    for(i=0; i<num; i++) {
      if( j>=n ) buff[i] = half_ptr[k++];
      else if( k>=(num-n) ) buff[i] = front_ptr[j++];
      else {
        if( half_ptr[k] > front_ptr[j] ) buff[i] = front_ptr[j++];
        else buff[i] = half_ptr[k++];
      }
    }

    free(front_ptr);
    free(half_ptr);
  }

  return 0;
}

